#include <stdio.h>
#include <stdlib.h>

typedef int Data;

typedef struct btree
{
	Data val;
	struct btree *left;
	struct btree *right;
} btree_t;


int init_tree(btree_t **tree)
{
	*tree = malloc(sizeof(btree_t));
	return 0;
}

int add_to_tree(btree_t **root, Data val)
{
	if(!root) return -1;

	btree_t *node = NULL;
	btree_t *tree = NULL;

	tree = *root;

	if (val < tree->val)
	{
		if(!tree->left) 
		{
			node = malloc(sizeof(btree_t));
			node->val = val;
			tree->left = node;
		}
		else 
		{
			add_to_tree(&tree->left, val);
		}
	}
	else if(val > tree->val)
	{
		if(!tree->right) 
		{
			node = malloc(sizeof(btree_t));
			node->val = val;
			tree->right = node;
		}
		else 
		{
			add_to_tree(&tree->right, val);
		}
	}
	else
	{
		printf("the node exist\n");
	}

	return 0;	
}


btree_t * find_from_tree(btree_t *tree, Data val, btree_t **parent)
{
	if(!tree) return NULL;

	if(val < tree->val) {

		if(tree->left) {
			if(parent) *parent = tree;
			return find_from_tree(tree->left, val, parent);
		} else {
			printf("node %d not exist!\n", val);
		}

	} else if (val > tree->val) {

		if(tree->right) {
			if(parent) *parent = tree;
			return find_from_tree(tree->right, val, parent);
		} else { 
			printf("node %d not exist!\n", val);
		}

	} else {
		printf("find the node %d parent %d success\n", tree->val, *parent ? ((btree_t *)*parent)->val : -1);
		return tree;
	}

	return NULL;	
}


int print_tree(btree_t *tree)
{
	static int i=2;
	int j=0;

	if(!tree) return 0;

	for (j=0;j<i;j++)
	{
		printf("    ");
	}

	printf("%d\n", tree->val);
	i--;
	print_tree(tree->left);
	i++;
	i++;
	print_tree(tree->right);

	return 0;
}

btree_t * find_right_biggest(btree_t *root)
{
	btree_t *node;

	node = root;
	while(node->right)
	{
		node = node->right;
	}

	return node;
}

int del_from_tree(btree_t **root, Data val)
{
	if(!root) return -1;

	btree_t *parent = NULL;
	btree_t *node = find_from_tree(*root, val, &parent);

	if(!node) printf("node %d not exist\n", node->val);

	if(!node->left && !node->right)
	{
		if(parent && parent->left == node)
			parent->left = NULL;
		else if(parent && parent->right == node)
			parent->right = NULL;
	}
	else if(node->left && !node->right)
	{
		if(parent && parent->left == node)
			parent->left = node->left;
		else if(parent && parent->right == node)
			parent->right = node->left;
	}
	else if(!node->left && node->right)
	{
		if(parent && parent->left == node)
			parent->left = node->right;
		else if(parent && parent->right == node)
			parent->right = node->right;
	}
	else if(node->left && node->right)
	{
		btree_t *biggest = find_right_biggest(node->left);
		del_from_tree(root, biggest->val);
		if(parent && parent->left == node)
		{
			parent->left = biggest;
		}
		else if(parent && parent->right == node)
		{
			parent->right = biggest;
		}
		biggest->left = node->left;
		biggest->right = node->right;

		if(!parent)
			*root = biggest;
	}

	
	return 0;
}

int main(int argc, char **argv)
{

	btree_t *btree = NULL;
	btree_t *parent = NULL;
	
	init_tree(&btree);
	btree->val = 30;

	add_to_tree(&btree, 40);
	add_to_tree(&btree, 10);
	add_to_tree(&btree, 45);
	add_to_tree(&btree, 3);
	add_to_tree(&btree, 12);
	add_to_tree(&btree, 42);
	add_to_tree(&btree, 50);
	add_to_tree(&btree, 46);

	print_tree(btree);
	find_from_tree(btree, 30, &parent);

	del_from_tree(&btree, 30);

	find_from_tree(btree, 30, &parent);
	print_tree(btree);

	return 0;
}
